package com.example.sorts11.sort;

/**
 * 插入排序（从头至尾搜索）
 * @auther lijiewei
 * @date 2021/8/24 18:01
 */
public class InsertionSortAdd {

    /**
     * 查询插入位置，从头到尾搜索（比从尾到头多耗费空间）
     * @param data 数组
     * @return
     * @author lijiewei
     * @date   2021/8/25 10:57
     */
    public static void fromStartToEnd(int[] data) {
        //循环排序
        for (int i= 1; i<data.length; i++) {
            //被比较的值
            int value = data[i];

            //临时数组，用于存放移位数据
            int[] tmp = new int[2];
            //交换的下标
            int change = i;
            //循环比较值查找交换位
            for (int j = 0; j < i; j++) {
                if (value >= data[j]) {
                    continue;
                }
                //临时数组中换着存
                int index = j%2;
                //第一次找到要交换的数据，
                if (change == i) {
                    tmp[Math.abs(index-1)] = data[j];
                    change = j;
                }
                tmp[index] = data[j+1];
                //其实是将data[j]中数据放入data[j+1]
                if (index == 0) {//判断是因为，都用index+1会越界
                    data[j+1] = tmp[index+1];
                } else {
                    data[j+1] = tmp[index-1];
                }
            }
            data[change] = value;
        }
    }
}
